package dp

func canPartition(nums []int) bool {
	var dp [10001]int
	var sum int
	for _, num := range nums {
		sum += num
	}
	if sum%2 == 1 {
		return false
	}
	for i := 0; i < len(nums); i++ {
		for j := sum / 2; j >= nums[i]; j-- {
			dp[j] = max(dp[j], nums[i]+dp[j-nums[i]])
		}
	}
	return dp[sum/2] == sum/2
}
